{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "from IPython.core.interactiveshell import InteractiveShell\n",
    "InteractiveShell.ast_node_interactivity = \"all\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['sld', 'hea', 'sld', 'hea', 'trh', 'trh', 'sld', 'trh', 'iar', 'trh', 'trh', 'hea', 'iar', 'sld', 'trh', 'hea', 'iar', 'hea', 'iar', 'hea', 'sld', 'iar', 'sld', 'iar', 'hard', 'this', 'real', 'hard', 'this', 'real']\n"
     ]
    }
   ],
   "source": [
    "import itertools\n",
    "from typing import List\n",
    "\n",
    "# '''\n",
    "# [\n",
    "#    \"this\",\n",
    "#    \"real\",\n",
    "#    \"hard\"\n",
    "# ]\n",
    "# '''\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        # 长度单词字典\n",
    "        word_dict = {}\n",
    "        for word in words:\n",
    "            if len(word) not in word_dict:\n",
    "                word_dict[len(word)] = []\n",
    "            word_dict[len(word)].append(word)\n",
    "        #print(word_dict)\n",
    "\n",
    "        res = []\n",
    "\n",
    "        # 遍历长度单词字典\n",
    "        for length, word_list in word_dict.items():\n",
    "            # 先不考虑重复问题，只考虑最特殊的，矩形的单词的行字符串的个数=列字符串的长度\n",
    "            # 考虑重复，不够则遍历重复采样补齐，多则遍历删除\n",
    "            # 得到word_list全排列的结果\n",
    "            word_list__permute_list = [wlp.split(\",\") for wlp in list(\n",
    "                map(','.join, itertools.permutations(word_list)))]\n",
    "            #print(word_list__permute_list)\n",
    "            row = len(word_list)  # 3 重复或删除\n",
    "            col = length  # 4\n",
    "            for word_list_permute in word_list__permute_list:\n",
    "                for i, row_word in enumerate(word_list_permute):\n",
    "                    if col == len(word_dict[row]):\n",
    "                        col_word_list = word_dict[row]\n",
    "                        # 获取col_word_list单词列表中，每个单词的第i个字符，并得到单词列表。\n",
    "                        col_str_list = [word[i] for word in col_word_list]\n",
    "                        # 得到col_str_list的全排列结果,可以提前计算存储起来，\n",
    "                        # col_str_list__permute = [cslp.split(\",\") for cslp in list(map(','.join, itertools.permutations(col_str_list)))]\n",
    "                        col_str_list__permute = list(\n",
    "                            map(''.join, itertools.permutations(col_str_list)))\n",
    "                        #print(col_str_list__permute)\n",
    "                        if row_word in col_str_list__permute:\n",
    "                            #print(row_word, col_str_list__permute.index(row_word))\n",
    "                            res.append(row_word)\n",
    "                            #print(res)\n",
    "                        else:\n",
    "                            continue\n",
    "        return res\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # words = [\"this\", \"real\", \"hard\", \"trh\", \"hea\", \"iar\", \"sld\"]\n",
    "    words = [\"iar\",\"trh\", \"sld\",\"real\", \"hea\",  \"this\", \"hard\"]\n",
    "    s = Solution()\n",
    "    res = s.maxRectangle(words)\n",
    "    print(res)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
